1. Field of the Invention
The present invention relates generally to data transmission and data storage. More specifically, the present invention relates to a system for the compression and decompression of digitized data using an array of single instruction multiple data parallel processors having mesh interconnected communications links.
2. Description of the Prior Art
Digital data compression system are useful to reduce the number of bits required to represent a signal in digital form. Digital data is typically compressed to either facilitate transmission of the signal through a limited-bandwidth communications channel or to reduce the amount of memory needed to store that signal on some archival media such as a computer hard disk.
Compression of digitized data can be achieved using either lossless or lossy coding techniques. Lossless coding involves only the extraction of statistical redundancy from the signal, and, thus, the amount of compression possible is signal dependent. For example, compression ratios of 2:1 are common for natural images whenever digital data representative of natural images is compressed using lossless coding techniques.
To obtain higher levels of compression of digital data or to code the signal at a fixed bit rate, some distortion must be accepted in the reconstructed signal, resulting in a loss of information when the signal is passed through an encoding system and then a decoding system. The goal of a lossy coding system, then, is to minimize the distortion introduced into the signal at all bit rates for which the lossy coding system is designed to operate, that is the user wants the best rate-distortion performance possible.
A variety of image compression algorithms and systems have been proposed in recent years. Many of the algorithms with the best rate-distortion performance such as the Joint Photographics Experts Group (JPEG) and Zerotree Coders use transforms to decorrelate image pixels before coding of the data. The JPEG standard relies on a block-based discrete cosine transform.
The zerotree coder uses a multiresolutional wavelet transform and takes advantage of the correlation between insignificant coefficients at different scales. U.S. Pat. No. 5,315,670 to James M. Shapiro discloses a digital data processing system which includes means for generating a tree structure of data representative coefficients with the tree structure having multiple paths from coefficients generated at a level of coarsest information to coefficients generated at a level of relatively finer information. The coefficients are evaluated to distinguish between significant and insignificant coefficients. Means are also included for generating a dedicated symbol representing a related association of insignificant coefficients within the tree structure, from a root coefficient of the tree structure to a set of end coefficients of the tree structure. The symbol represents that neither the root coefficient of the tree structure nor any descendant of the root coefficient has a magnitude greater than a given reference level. A coefficient is considered to be insignificant and a "root of a zerotree", whereby all descendants are predictably insignificant, if (a) the coefficient has an insignificant magnitude, (b) the coefficient is not the descendant of a root from a coarser level, and (c) all the descendants of the coefficient at finer levels have insignificant magnitudes. A coefficient found to be a zerotree root is coded with a dedicated symbol which is eventually processed by an entropy coder.
In addition, a coding algorithm based on the wavelet packet transform has recently been used to achieve the best rate-distortion performance to date on certain difficult images which require encoding.
While wavelet based compression systems generally perform adequately for their intended purpose of data compression, these wavelet-based systems are more computationally complex than systems for data compression that are based on a discrete cosine transform. The complexity of wavelet based compression systems can significantly limit real-time performance. Further, the complexity of wavelet based compression systems can significantly increase the cost of a system designed to achieve a specified performance goal.
The best (in a rate-distortion sense) wavelet-based algorithm currently available is the embedded zerotree wavelet (EZW) algorithm developed by James M. Shapiro while employed at Sarnoff Labs. Unfortunately, this algorithm executes more slowly than many other wavelet-based algorithms because of its high structural complexity, that is the embedded zerotree wavelet algorithm has a lot of repetitive scanning. Thus, implementing this sequential algorithm to achieve a high throughput rate (e.g., many image frames per second) requires very advanced processors and may be impossible to implement for the desired throughput rate.
Thus there is a need for a data compression system which will achieve high throughput speeds, scalability and efficiency in very large scale integration implementations. The data compression system should also have a compression performance equal to the sequential EZW algorithm and also should be able to provide higher throughput at a substantially reduced cost.